package org.example.字符串匹配字串出现的索引位置;

import java.util.Arrays;

public class KMP算法 {

	public static void main(String[] args) {
		System.out.println(Arrays.toString(computeNext("qweq")));
	}

	public static int kmpMatch(String host, String child) {
		int n = host.length();
		int m = child.length();
		int[] next = computeNext(child);

		int i = 0, j = 0;
		while (i < n) {
			if (host.charAt(i) == child.charAt(j)) {
				i++;
				j++;
				if (j == m) {
					return i - j;
				}
			} else {
				if (j != 0) {
					j = next[j - 1];
				} else {
					i++;
				}
			}
		}
		return -1;
	}

	private static int[] computeNext(String child) {
		int m = child.length();
		int[] next = new int[m];
		int len = 0;
		int i = 1;

		while (i < m) {
			if (child.charAt(i) == child.charAt(len)) {
				len++;
				next[i] = len;
				i++;
			} else {
				if (len != 0) {
					len = next[len - 1];
				} else {
					next[i] = 0;
					i++;
				}
			}
		}
		return next;
	}

}
